#include<iostream>
#include<vector>
using namespace std;
struct ListNode 
{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
bool hasCycle(ListNode *head) 
{
	ListNode* p1 = head;
	ListNode* p2 = head;
	while (p2!=nullptr && p2->next != nullptr) //取快指针
	{
		p1 = p1->next;
		p2 = p2->next->next;
		if (p1 == p2)
		{
			return true;
		}
	}

	return false;
}

//链表是否有环检测
bool JustCycle(ListNode* head)
{
	ListNode* p1 = head;
	ListNode* p2 = head;
	while (p2 != NULL && p2->next != NULL)
	{
		p1 = p1->next;
		p2 = p2->next->next;
		if (p1 == p2)
		{
			return true;
		}
	}

	return false;
}

//冒泡排序
void SortBase(vector<int>& s)
{
	int n = s.size();
	for (int i = 0; i < n; i++)
	{
		//for (int j = 0; j < n - 1; j++)
		for(int j = 0;j<(n-1-i);j++)  //优化的，少去无用的遍历，类似堆排序后面的调整堆
		{
			if (s[j] > s[j + 1])
			{
				swap(s[j], s[j + 1]); //最大的一个一定是在最后面，所以可以优化的。类似堆排序
			}
		}
	}

}

void AdjustHeap410(vector<int>& s,int base,int n)
{
	int parent = base;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && s[child] < s[child + 1])
		{
			child = child + 1;
		}

		if (s[child] > s[parent])
		{
			swap(s[child], s[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//一定要有这一步
		}
	}
}
//堆排序
void HeapSort410(vector<int>& s)
{
	int n = s.size();
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) //注意这里是n-1-1  后面是i--
	{
		AdjustHeap410(s,i,n);
	}

	for (int i = n - 1; i > 0; i--) //注意这里是大于0，因为每次要和0交换
	{
		swap(s[i], s[0]);
		AdjustHeap410(s, 0, i);
	}
}
int GetPartation(vector<int>& s,int left,int right)
{
	int base = s[left];
	int i = left;
	int j = right;
	while (i < j)
	{
		while (i < j && s[j] >= base)
		{
			j--;
		}
		s[i] = s[j]; //1
		while (i < j && s[i] <= base)
		{
			i++;
		}
		s[j] = s[i];//2


	}

	s[i] = base;//3   这三个交换看成一体的就不会漏掉了
	return i;
}
//快速排序
void QuickSort410(vector<int>& s,int left,int right)
{
	//要有框架在脑海
	if (left < right)
	{
		int mid = GetPartation(s,left,right);
		QuickSort410(s,left,mid-1);
		QuickSort410(s, mid + 1, right);
	}
}

int main()
{
	vector<int> s = { 30,4,45,6,0,-2,66,45 };
	//SortBase(s);
	//HeapSort410(s);
	QuickSort410(s, 0, s.size() - 1);
	for (int i = 0; i < s.size(); i++)
	{
		cout << s[i] << " ";
	}
	cout << endl;
	return 0;
}